#include "Tree.h"

#include <iostream>
#include <bitset>
#include <string>

using namespace Huffman;
using namespace std;

Node* Tree::NYT = new Node(); /* Not Yet Transmitted */
Node* Tree::EOC = new Node(); /* End Of Coding */

Tree::Tree(void)
{
	itCounter = 1;
	setRoot(NYT);

	Node* top = new Node();
	top -> setLeft(NYT);
	top -> setRight(EOC);
	top -> setNodeType(INTERNAL);

	NYT -> setParent(top);
	NYT -> setNext(EOC);
	NYT -> setParity(0);	

	EOC -> setParent(top);
	EOC -> setPrev(NYT);	
	EOC -> setNext(top);	
	EOC -> setParity(1);	
	EOC -> setWeight(1);

	setRoot(top);

	freeze = false;
}

Tree::~Tree(void)
{
	// empty destructor
}

void Tree::setRoot(Node* n)
{
	this -> root = n;
}
		
Node* Tree::getRoot() const 
{
	return root;
}

void Tree::updateTreeVitter(char symbol){	

	if(freeze) {
		return;
	}

	Node* leafToIncrement = NULL;
	Node* p = findNode(symbol);	
	Node* symbolNode;
	if ( p == 0 ){ /* a new symbol */

		// creates a node for storing the newly added symbol
	    symbolNode = new Node();

		// creates new node for the both the symbol	and new NYT node
		Node* top = new Node();		
		top -> setParent(NYT -> getParent());
		top -> setLeft(NYT);
		top -> setRight(symbolNode);
		top -> setWeight(0); //NYT -> getWeight() is the same as 0, by default
		top -> setParity(0); //NYT -> getParity() is the same as 0, by deafult 		
		top -> setNodeType(INTERNAL);

	    top -> setNext(NYT -> getNext());
		top -> setPrev(symbolNode);

		symbolNode -> setParent(top);
		symbolNode -> setSymbol(symbol);
		symbolNode -> setWeight(0);
		symbolNode -> setParity(1);

	    symbolNode -> setPrev(NYT);
	    symbolNode -> setNext(top); 
		
		NYT -> setNext(symbolNode);	
		NYT -> setParent(top);

		if ( getRoot() == NYT ){ //to bedzie tylko raz na poczatku, pozniej root juz nie bedzie sie zmienial
			setRoot(top);
		}

		p = symbolNode -> getParent();
		leafToIncrement = p -> getRight();

	} else { /* swap p in tree with leader of its block */						

		/* Note that two node are in same block if have same  equal weights and ( both are leafs or both are internal nodes ) */
		slideHigherThanLeafNodesWithWeight(p,p -> getWeight() );
		
		/* if p is the sibling of NYT node */
		if ( NYT -> getNext() == p ){			
			leafToIncrement = p;
			p = p -> getParent();
		}
	}
	
	displayNode();

	while ( p != getRoot() ){
		/* if possible advance p to the next block */	
		p = slideAndIncrement(p);

		displayNode();
	}

	if ( leafToIncrement != 0 ){		
		slideAndIncrement( leafToIncrement );
	}

	// adds the node to the map
	nodeMap.insert(std::pair<char, Node*>(symbol, symbolNode)); 	
}

Node* Tree::slideAndIncrement(Node *p){	
	Node* fp = p -> getParent();
	int wt = p ->getWeight();
	
	if ( p -> getNodeType() == INTERNAL ){ 		
		slideHigherThanLeafNodesWithWeight(p,wt + 1);		
		slideInternalNode(p, wt);
	} else {		
		slideHigherThanNodesWithWeight(p,wt);		
	}
	
	p -> setWeight(p -> getWeight() + 1);

	if ( p -> getNodeType() == INTERNAL ){ 		
		p = fp;
	} else {		
		p = p -> getParent(); // p = new parent of p
	}

	return p;
}

Node* Tree::slideHigherThanLeafNodesWithWeight(Node* p, unsigned long weight){	
	Node* nextNodeInBlock = NULL;
	Node* nextNode = p -> getNext();
	 			
	while ( nextNode && nextNode -> getNodeType() == LEAF && nextNode -> getWeight() <= weight  ){ // root is not leaf
		nextNodeInBlock = nextNode; 
		nextNode = nextNodeInBlock -> getNext();
	}

	if ( nextNodeInBlock && p-> getParent() != nextNodeInBlock ){
		swapNodes(p,nextNodeInBlock);
	}

	return p;
}

Node* Tree::slideHigherThanNodesWithWeight(Node* p, unsigned long weight){
	Node* nextNodeInBlock = NULL;
	Node* nextNode = p -> getNext();
	 			
	while ( nextNode && nextNode -> getWeight() <= weight  && nextNode != getRoot() ){
		nextNodeInBlock = nextNode;
		nextNode = nextNodeInBlock -> getNext();
	}

	if ( nextNodeInBlock && p-> getParent() != nextNodeInBlock ){ //dodatkowy bufor bezpieczenstwa
		swapNodes(p,nextNodeInBlock);
	}

	return p;
}

Node* Tree::slideInternalNode(Node* p, unsigned long weight){	
	Node* nextNodeInBlock = NULL;
	Node* nextNode = p -> getNext();
	 			
	while ( nextNode && nextNode -> getWeight() <= weight  ) {
		nextNodeInBlock = nextNode; 
		nextNode = nextNodeInBlock -> getNext();
	}

	if ( nextNodeInBlock && p-> getParent() != nextNodeInBlock ){
		swapNodes(p,nextNodeInBlock);
	}

	return p;
}

void Tree::printOnConsole(){	
	
	displayNode();

	itCounter++;
}

void Tree::displayNode() {

	return;
	map<char, Node*>::iterator p;
  
	std::cout << itCounter << "<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n" ;	
	Node * it = getRoot();
	while ( it -> getPrev() != 0) {
		std::cout << "(" << it -> getSymbol() << "," << it -> getWeight()  << ")";
		// std::cout << "[Id: "<< it -> getId() << " (" << it -> getSymbol() << "," << it -> getWeight()  << ") L:"<< getId(it -> getLeft()) <<" R:"<< getId(it -> getRight()) <<"], ";
		it = it -> getPrev();		
	}
	std::cout << "\n";

	//for(p = nodeMap.begin(); p != nodeMap.end(); p++) {				

	//	int parent = p -> second -> getParent() != 0 ? p -> second -> getParent() -> getId() : -1;
	//	int left = p -> second -> getLeft() != 0 ? p -> second -> getLeft() -> getId() : -1;
	//	int right = p -> second -> getRight() != 0 ? p -> second -> getRight() -> getId() : -1;		
	//	/*int next = p -> second -> getNext() != 0 ? p -> second -> getNext() -> getId() : -1;*/
	//	/*int prev = p -> second -> getPrev() != 0 ? p -> second -> getPrev() -> getId() : -1;		*/
	//	int next  = -1;
	//	int prev = -1;
	//	// << "	parent|left|right|next|prev: "  p -> second ->getId() 
	//	std::cout << p -> first << ":" <<  getStrFromNode(p -> second) << "	" << "	"<<  p -> second ->getParity() << "\t\t" << parent <<  " | "<< left << " | "<< right << " | " << std::endl;		
	//}
	std::cout << "<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n" ;
}

int Tree::getId(Node* n) {
	return n != 0 ? n -> getId() : 0;
}

string Tree::getStrFromNode(Node* node) {

	string result = "";	
	//int bitCount = 0;
	//std::bitset<16> bitsetObject;
	//if ( node -> getParent() == 0 && node == symbolTree -> getRoot() ){
	//	return node->getSymbol(); //NYT
	//}

	while(node -> getParent() != 0) {
		/*std::cout << "		Getting parent" << "\n";*/
		
		if ( node -> getParity() ){
			result += "1";
		} else {
			result += "0";
		}

		node = node -> getParent();
		//bitsetObject[0]
		//bitCount++;
	}
	/*std::cout << "		Returning" << "\n";*/

	string reverseStr = "";	
	string::reverse_iterator It = result.rbegin();
    while ( It != result.rend() ){
		reverseStr += *It++;    
	}
        

	return  reverseStr; 	
}

void Tree::swapNodes(Node* node, Node* nextNode){	


	/*if ( node -> getWeight() > nextNode -> getWeight() ) {
		std::cout << node -> getWeight() << "  -> " << nextNode -> getWeight() << std::endl;
	}*/
	Node* tmpNext = node -> getNext();	
	Node* tmpPrev = node -> getPrev();	
	Node* tmpParent = node -> getParent();	
	int tmpParity = node -> getParity();	
	
	Node* nextNodeParent = nextNode -> getParent();

	if ( node -> getNext() == nextNode ) {
		
		node -> setNext(nextNode -> getNext() );
		nextNode -> getNext() -> setPrev(node);

		node -> setPrev(nextNode);					
		tmpPrev -> setNext(nextNode);		
		
		nextNode -> setNext(node);
		nextNode -> setPrev(tmpPrev);				

	} else {

		node -> setNext( nextNode -> getNext() );
		node -> setPrev( nextNode -> getPrev() );

		nextNode -> getNext() -> setPrev(node);
		nextNode -> getPrev() -> setNext(node);

		nextNode -> setNext(tmpNext);
		nextNode -> setPrev(tmpPrev);

		tmpNext->setPrev(nextNode);
		tmpPrev->setNext(nextNode);	

	}

	/* swap parities and  parent left,right  */
	if ( node -> getParity() ){
		node -> getParent() -> setRight(nextNode);
	} else {
		node -> getParent() -> setLeft(nextNode);
	}

	if ( nextNode -> getParity() ){
		nextNode -> getParent() -> setRight(node);
	} else {
		nextNode -> getParent() -> setLeft(node);
	}

	node -> setParity( nextNode -> getParity() );
	nextNode  -> setParity(tmpParity);

	/* swap parents */	
	if ( node -> getParent() == nextNode ) {

		tmpParent = nextNode -> getParent();
		node -> setParent( tmpParent );
		nextNode -> setParent(node);
	} else if(nextNode -> getParent() == node) {

		tmpParent = node -> getParent();
		node -> setParent(nextNode);
		nextNode -> setParent(tmpParent);
	} else {

		node -> setParent( nextNode -> getParent() );
		nextNode -> setParent(tmpParent);
	}
}


Node* Tree::findNode(char symbol) 
{
	std::map<char,Node*>::iterator it;

	it = nodeMap.find(symbol);

	// returns the found node or NULL (zero)
	return it != nodeMap.end() ? it->second : 0;
}

void Tree::setMaxAllowedWeight(unsigned long weight)
{
	this -> maxAllowedWeight = weight;
}

unsigned long Tree::getMaxAllowedWeight() 
{
	return maxAllowedWeight;
}

void Tree::checkWeight()
{
	if(getRoot() != 0 
		&& getRoot() -> getRight() != 0 
		&& getRoot() -> getRight() -> getWeight() > maxAllowedWeight) {

			freezeTree();
	}
}

void Tree::freezeTree() 
{
	freeze = true;
}